package 算法.leetcode.offer.nk;

import 算法.leetcode.offer.base.ListNode;

/**
 * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * 数据范围： 0 \le n \le 10000≤n≤1000，-1000 \le 节点值 \le 1000−1000≤节点值≤1000
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 *
 * @author lchenglong
 * @date 2022/3/22
 */
public class BM4 {
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0),cur = head;
        while(list1!=null&&list2!=null){
            cur.next = list1.val>=list2.val?list1:list2;
            ListNode next = null;
            if(list1.val<list2.val){
                next = list1;
                list1 = list1.next;
            } else {
                next = list2;
                list2 = list2.next;
            }
            cur.next = next;
            cur = cur.next;
        }
        cur.next = list1==null?list2:list1;
        return head.next;

    }
}
